package com.hdu.other.dp.one;

public class lc264 {
    class Solution {
        public int nthUglyNumber(int n) {
            int[] ans = new int[n + 1];
            ans[1] = 1;
            for (int i = 2, index1 = 1, index2 = 1, index3 = 1; i <= n; i++)
            {
                int num1 = ans[index1] * 2;
                int num2 = ans[index2] * 3;
                int num3 = ans[index3] * 5;
                int cur = Math.min(
                        Math.min(
                                num1,
                                num2
                        ),
                        num3
                );
                ans[i] = cur;
                if (cur == num1)
                {
                    index1++;
                }
                if (cur == num2)
                {
                    index2++;
                }
                if (cur == num3)
                {
                    index3++;
                }
            }
            return ans[n];
        }
    }
}
